package 刷题10月.二叉树;
import java.util.*;
//https://blog.csdn.net/dingzhi4469/article/details/118497337?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.no_search_link&spm=1001.2101.3001.4242
//https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=117&&tqId=37819&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
public class NC45实现二叉树先序中序和后序遍历1001 {



      public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
      }


    public class Solution {
        /**
         *
         * @param root TreeNode类 the root of binary tree
         * @return int整型二维数组
         */
        public int[][] threeOrders (TreeNode root) {
            // write code here

            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            List<Integer> list3 = new ArrayList<>();

            preOrder(root, list1);
            inOrder(root, list2);
            postOrder(root, list3);

            int[][] res = new int[3][list1.size()];
            for(int i = 0; i < list1.size(); i++){
                res[0][i] = list1.get(i);
                res[1][i] = list2.get(i);
                res[2][i] = list3.get(i);

            }

            return res;
        }
        // 先序遍历
        public void preOrder(TreeNode root, List<Integer> list){
            if(root == null){
                return;
            }
            list.add(root.val);
            preOrder(root.left, list);
            preOrder(root.right, list);
        }

        // 中序遍历
        public void inOrder(TreeNode root, List<Integer> list){
            if(root == null){
                return;
            }

            inOrder(root.left, list);
            list.add(root.val);
            inOrder(root.right, list);
        }

        // 后序遍历
        public void postOrder(TreeNode root, List<Integer> list){
            if(root == null){
                return;
            }

            postOrder(root.left, list);
            postOrder(root.right, list);
            list.add(root.val);
        }

    }
}
